package com.shm.leetcode;

/**
 * 二叉查找树中第 K 小的元素 II
 * 给定一个二叉搜索树，我们希望找到其中第 k 小的元素。
 *
 * 在这道题目中，除了原始的二叉搜索树 root 以外，你还会得到一个和其结构完全一致的二叉树 nodenum_root，树上节点的值代表以该节点为根的子树的节点数量。
 *
 *
 *
 *
 *
 * 示例：
 *
 *
 * 输入：root = [5,3,8,2,3], nodenum_root = [5,3,1,1,1], k = 3
 * 输出：3
 * 解释：第三小的数为 3
 *
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/5hhxs5/
 * @author SHM
 */
public class KthSmallestII {
    int k,res;
    public int kthSmallestII_1(TreeNode root, TreeNode nodenum_root, int k) {
        this.k=k;
        dfs(root);
        return res;
    }

    void dfs(TreeNode root){
        if(root==null){
            return;
        }
        dfs(root.left);
        k--;
        if(k==0){
            res =  root.val;
        }
        dfs(root.right);
    }

    /**
     * 题目解析
     * 现在我们知道了以每个节点为根的子树的节点数量，那么根据当前根节点左右子树的节点数量以及 k，我们可以直接推断出目标点在当前节点的左子树还是右子树上。这样就可以直接递归下去找到目标点，时间复杂度从 O(n)O(n) 降低为 O(h)O(h)，hh 为树的高度。
     *
     * 作者：力扣 (LeetCode)
     * 链接：https://leetcode-cn.com/leetbook/read/high-frequency-algorithm-exercise/5hhjg6/
     * @param root
     * @param nodenum_root
     * @param k
     * @return
     */
    public int kthSmallestII(TreeNode root, TreeNode nodenum_root, int k) {
        int curOrder = nodenum_root.val - (root.right == null ? 0 : nodenum_root.right.val);
        if (curOrder == k) {
            return root.val;
        } else if (curOrder > k) {
            return kthSmallestII(root.left, nodenum_root.left, k);
        } else {
            return kthSmallestII(root.right, nodenum_root.right, k - curOrder);
        }
    }
}
